package codingInterview.leetcode.editor.cn;

//输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。 
//
// 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 12
//输出：5
// 
//
// 示例 2： 
//
// 
//输入：n = 13
//输出：6 
//
// 
//
// 限制： 
//
// 
// 1 <= n < 2^31 
// 
//
// 注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/ 
// Related Topics 递归 数学 动态规划 👍 295 👎 0

//Java：剑指 Offer 43 - 1～n 整数中 1 出现的次数
public class OneNzhengShuZhong1chuXianDeCiShuLcof{
    public static void main(String[] args) {
                Solution solution = new OneNzhengShuZhong1chuXianDeCiShuLcof().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int countDigitOne(int n) {
        if(n>=1 && n<10) return 1;
        char[] numbers = String.valueOf(n).toCharArray();
        int count = 0;
        for (int i = 0; i < numbers.length; i++) {
            char number = numbers[numbers.length-i-1];
//            System.out.println(number-'0');
            if(number > '1' && number<='9'){
                count+= (int)(n/(Math.pow(10,i+1)) +1)*Math.pow(10,i);
            }else if (number == '1'){
                count+= (int)(n/Math.pow(10,i+1))*Math.pow(10,i) + n%Math.pow(10,i)+1;
            }else if(number == '0'){
                count+= (int)(n/(Math.pow(10,i+1)))*Math.pow(10,i);
            }
//            System.out.println(count);
        }
        return count;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
